The present invention relates generally to design automation, and relates more particularly to statistical timing of integrated circuit (IC) chips.
As part of statistical timing, a static timing analysis tool needs to compute the extrema (i.e., maximum and/or minimum) of several random variables that represent timing data. FIG. 1A, for example, is a schematic diagram illustrating a NAND gate 100 with three inputs A, B, and C and output Z. The latest arrival time at the output Z (i.e., ATZ) is computed as the statistical maximum of the arrival times of signals from the inputs A, B, and C (i.e., ATA, ATB, and ATC, respectively).
During the chip timing closure process, and especially during fix-up or optimization, incremental changes (e.g., buffer insertion, pin swapping, layer assignment, cell sizing, etc.) are made to the IC chip. Typically, the timing data at only one of the inputs on which the extrema needs to be computed at any given timing point is changed; however, the change must be propagated. FIG. 1B, for example, is a schematic diagram illustrating the insertion of a buffer 102 at one of the inputs (i.e., input A) to the NAND gate 100 of FIG. 1A. The insertion of the buffer 102 requires the timing analysis tool to re-compute the arrival time at the output Z (i.e., ATZnew, or the statistical maximum of the arrival times ATAnew, ATB, and ATC).
Conventional timing analysis methods force a re-computation of the maximum of all of the input timing data. This is computationally very expensive, especially when the number of input random variables that represents the timing data is very large (e.g., as in the case of several signals from a multiple-input gate propagating to the output, or a multiple fan-out net emanating from a single output pin of a gate). Even where only one of the inputs has changed (e.g., as in FIG. 1B), the timing analysis tool is forced to re-compute the extrema of all inputs, including those inputs that are unchanged. For an optimization tool making millions of incremental changes in a large design, this re-computation of unchanged input data is very inefficient and leads to waste of machine resources.
Thus, there is a need in the art for a method and apparatus for efficient incremental statistical timing analysis and optimization.